
%!TEX root = main.tex

\section{INTRODUCTION}\label{sec:Introduction}


%The ubiquitous fusion of social media and the internet has resulted in large-scale user-generated data from minute to minute,
%and the social network platform (SNP) extends its capability as a social media in reporting real-time news due to the advent of mobile technology \cite{Magnani:2010:News}.
With the rise of online social networks, Internet users are shifting from searching on traditional media to social network platforms (SNPs) to retrieve up-to-date and valuable information~\cite{UserSearchShiftChanged}. For example, one may search on Twitter to see the latest news and
comment on Malaysia airlines flight MH17. However, searching SNP data is rather challenging due to its unique properties: not only containing user-generated contents from time to time, but also having a complex graph structure. Particularly there are two distinguishing characteristics:
\begin{itemize}
%\item \textbf{Huge Volume}: Facebook has over 1.3 billion users in 2014\footnote{http://www.statisticbrain.com/facebook-statistics/}. Each user is associated with high volume of text, multimedia, spatial data and social graphs etc.
\item \textbf{High Update Rate}: Twitter has over 288M active users with 400 million posts per day in 2013\footnote{http://www.statisticbrain.com/twitter-statistics/}. %\reminder{no recent data in 2013?it is better *** in a second}
%\item \textbf{Large volume}: Twitter or Facebook generate large data \reminder{add numbers}.
\item \textbf{Small World Phenomenon}: People in the social network are not very far away from each other. For Facebook, the average degrees of separation between users are 4.74\footnote{http://www.facebook.com/DegreesApp/}. Moreover, unlike traditional road networks where each vertex has a small degree, the vertex degree of a social network follows the power law distribution \cite{SocialAnalytics:Aggarwal:2011}.
%\item \textbf{Weighted Relationship}: Friends are not usually of equal importance in the real world. Weighted measure of the edge/relationship is a basic way to define social relation.
\end{itemize}

%\reminder{there three characteristics should link to the three dimensions.}

Top-k keyword search is an important tool for users to consume Web data. However, existing works on keyword search over social networks \cite{Twitter:Earlybird,NUS:TI,PersonSearch:Schenkel:2008:SIGIR,PersonSearch:Sihem:2008:VLDB,PersonSearch:Silviu:2013:CIKM} usually ignore one or many above characteristics of SNPs and lead to several weakness, e.g. returning user with meaningless or outdated search results, low query performance, providing global major trends but not personalized search results which may easily result in biased views~\cite{twitter_monitor}.
%Moreover, the current search tools tend to present global search results and major trends, which may result in a biased view \cite{twitter_monitor}, while personalized search which is aware of the social relevance provides more diversified views.
Thus, it calls for a general framework to provide real time personalized search over the social network data that leverages all unique characteristics of SNPs.

%When a user wants to seek opinions on ``MH17", they probably prefer to see views from their own circles first, i.e. their friends or friends of friends, rather than a global search over the whole SNP. Global search result shared by the majority

%Several attempts have been made to address the personalized top-k query on the SNPs where they all try to build indices according to the static textual information \cite{Bahmani:2012:PMB:2187836.2187891,Qiao:2013:TNK:2536206.2536217}. However, none of them is aware of the \textbf{highly dynamic} nature of the SNPs when designing index and query processing techniques.

As a preliminary effort, this paper focuses on three most important dimensions on SNPs: \textit{Time Freshness}, \textit{Social Relevance} and \textit{Text Similarity} in order to support the above two characteristics. \textit{Time Freshness} is an essential requirement as outdated information means nothing to the user in a highly dynamic SNPs. \textit{Social Relevance} must be adopted in the search framework as well, because leveraging the personal network to rank results will greatly improve the search experience as people tend to trust those who are \quotes{closer} and will also enable more user-interactions. For example,
a basketball fan is more likely to respond to a post on \quotes{NBA Finals} that is posted by a friend or friend's friend than
unfamiliar stranger.
%Besides, personalization also provides users more diversified views on the same event from different social groups.
Lastly \textit{Text Similarity} is the fundamental search dimension in top-k query where keywords are used to distinguish the results from available documents.

There are many challenges to support the search over these three dimensions.
First it is challenging to design an index structure that is update-friendly while supporting powerful pruning for instant query processing. Specifically, when a new document is posted, it must be made available immediately in the search index rather than being periodically loaded.
The second challenge lies in the query evaluation based on the index. In particular, how to enable an efficient computation along the social dimension, whose performance dominates its counterparts on the other two dimensions. The social distance is usually modeled as the
shortest distance on the social graph \cite{Qiao:2013:TNK:2536206.2536217,Bahmani:2012:PMB:2187836.2187891,Singla:2008:YCS:1367497.1367586,PersonSearch:Sihem:2008:VLDB,PersonSearch:Schenkel:2008:SIGIR}.
Two straightforward solutions are either computing on the fly or pre-computing all-pairs distances\reminder{add references}. The first is extremely inefficient for large networks, which renders it unacceptable for real-time response, while the latter requires prohibitively large storage. A natural way is to develop query processing techniques based on index with reasonable size. However, existing distance indices are unable to handle massive social network because they neglect one or many unique characteristics of the SNPs. This motivates us to develop an efficient algorithm for distance query which is aware of all aforementioned properties of social networks.


\Comment{Information on SNPs are highly heterogenous nowadays. For example, a simple tweet may contains information of text, temporal and spatial data, multi-media data like pictures and videos.}

\Comment{ Take LinkedIn for an example, Alice wants to search for a job position for \quotes{software engineer}. It is probably better to retrieve job offers that are posted most recently as earlier posts could have already been taken. Take LinkedIn for an example, Alice wants to search for a job position for \quotes{software engineer}. It is probably better to retrieve job offers that are posted most recently as earlier posts could have already been taken. Furthermore, imagining the job opportunity is posted by someone who is socially connected with Alice, e.g. Alice's friend or friend's friend, there is a higher chance for Alice to be shortlisted for this job offer than those from unfamiliar people.}


\Comment{Traditional Information Retrieval(IR) methods assume static data while the query is dynamically expressed in the form of keywords. Inverted lists that sort documents w.r.t. the keyword frequencies are often used to handle the top-k query \cite{TextSimilarity:Zobel}.}

\Comment{
\reminder{can the following be the discussion of the challenges?}
\reminder{then discuss the challenges!}
}

 %based on which the proposed query processing can guarantee a fast top-k evaluation as new data keep being ingested  An indispensable counterpart of the dynamic index is to develop an efficient query processing technique upon it, which is our second technical challenge.
%operates on the dynamic index and returns top-k results immediately after the query is submitted as new data keep being ingested into the system.


To address these challenges, we present a novel solution to support real time personalized top-k query on SNPs. The contributions of this paper are summarized as follows:
\begin{itemize}
\item We present a novel 3D cube inverted index to support efficient pruning on the 3 dimensions (time,social,textual) simultaneously. Such 3D index is capable of handling fast updates against high rate of document ingestion, while flexible in size w.r.t. different system preferences.
\item We design a general ranking function that caters to various user preferences on these 3 dimensions, and devise a cube threshold based algorithm (CubeTA) to retrieve the top-k results by such ranking function. CubeTA traverses the 3D lists using a best-effort strategy and returns the query results as early as possible. Our method has a generic design of ranking function, index and search algorithm. It enables opportunities to support personalized-only (regardless results' freshness) and real-time-only (regardless of social locality) search. It is also a good complement to the global search provided by existing SNPs.
\item We propose several optimizations to solve the aforementioned social distance problem. The optimizations answer a single distance query with an average of less than $1us$ for a graph with $10M$ vertices and over $230M$ edges.
\item We optimize the 3D index via a hierarchical partition method which enhances the pruning on the social dimension. A deeper partition tree will lead to better query performance and the flexibility of the index allows the space occupied to be the same as the basic 3D index.
\item We conduct extensive experimental studies on two real-world large datasets: Twitter and Memtracker. The results show that our proposed solution outperforms the two baselines with average 4-8x speedups.
\end{itemize}


%Note that our real-time personalized search feature is a good complement to the global search provided by existing SNPs.

In the rest of the paper, we present related work in Sec. \ref{sec:Related-Work} and problem definition in Sec. \ref{sec:ProblemDefinition}. We propose the 3D inverted index in Sec. \ref{sec:Index} and a basic search method called CubeTA in Sec. \ref{sec:qp}. In Sec. \ref{sec:ShortestPath} we propose several optimizations to speed up shortest distance query evaluation as part of CubeTA. We propose a hierarchical partition scheme for our 3D inverted index to optimize CubeTA in Sec. \ref{sec:HierarchicalPartition}, and report experiment results in Sec. \ref{sec:ExperimentResult}. Finally we conclude in Sec. \ref{sec:Conclusion}.
